Inwazja kosmitów
Limit pamięci: 128 MB
W Bajtockim Instytucie Egzobiologii powołano właśnie do życia Zakład Ostrzegania przed Niebezpieczeństwami z Kosmosu.
Zatrudnieni w nim naukowcy
mają za zadanie zrobić wszystko, aby uchronić obywateli Bajtocji przed skutkami inwazji kosmitów,
która niechybnie nastąpi.
W Bajtocji znajduje się miast, położonych wzdłuż Bajtodrogi.
Miasta będziemy numerować kolejno od 1 do .
W mieście o numerze mieszka obywateli.
Jak powszechnie wiadomo, kosmici zawsze atakują nocą, co najwyżej jedno miasto.
Niestety, ich atak jest natychmiastowy - wszyscy mieszkańcy zaatakowanego miasta zostają błyskawicznie porwani i wytransportowani
do galaktyki kosmitów.
Naukowcy w zakładzie pracują nad sposobem ochrony mieszkańców.
Ponieważ kosmitów nie interesują bajtockie gryzonie, naukowcy postanowili wykorzystać tresowane szczury do ostrzeżenia pozostałych miast w Bajtocji.
Gdy kosmici zaatakują jakieś miasto, dwa szczury wyruszą z tego miasta w przeciwnych kierunkach Bajtodrogi, niosąc wiadomość o napaści.
Przebiegnięcie jednego odcinka Bajtodrogi zajmuje im prawie cały dzień, wobec tego wiadomość
wysłana z miasta dotrze do miasta tuż przed zapadnięciem zmroku -tego dnia po ataku.
Zaalarmowani mieszkańcy chowają się do schronów, gdzie macki kosmitów ich nie dosięgną.
Ponieważ bajtockie schrony są dobrze zaopatrzone, ostrzeżeni mieszkańcy pozostaną w nich tak długo, aż kosmici zaprzestaną ataków i wrócą do swojej galaktyki.
Jak widać, opisany system niekoniecznie pozwoli uratować się wszystkim obywatelom Bajtocji.
Naukowcy zastanawiają się, ilu mieszkańców zostanie porwanych w najgorszym przypadku.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita
(), oznaczająca liczbę miast w Bajtocji.
W drugim wierszu znajduje się ciąg liczb całkowitych
().
Określają one liczby mieszkańców kolejnych miast położonych
wzdłuż Bajtodrogi.
Wyjście
W jedynym wierszu wyjścia należy wypisać liczbę całkowitą oznaczającą maksymalną
możliwą liczbę porwanych mieszkańców.
Przykład
Dla danych wejściowych:
6
5 9 1 3 7 2
poprawną odpowiedzią jest:
16
Autor zadania: Tomasz Idziaszek.